package com.cuz.hot100;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Q76minWindow {
    public static void main(String[] args) {
        //"ADOBECODEBANC"
        //"ABC"
        //"bba"
        //"ab"
        System.out.println(minWindow1("bba", "ab"));
    }

    public static String minWindow1(String t, String s) {
        //base case
        if (s == null || t == null
                || s.length() == 0 || t.length() == 0
                || s.length() > t.length()) {
            return "";
        }
        //寻找字符的个数map
        HashMap<Character, Integer> sMap = new HashMap<>();
        char[] sChars = s.toCharArray();
        //统计每个字符出现的个数
        for (char sChar : sChars) {
            sMap.put(sChar, sMap.getOrDefault(sChar, 0) + 1);
        }
        //当前滑动窗口字符个数
        HashMap<Character, Integer> tMap = new HashMap<>();
        char[] tChar = t.toCharArray();
        int left = 0;
        int right = 0;
        //结果
        String ans = null;
        //有效字符的个数 比如 寻找字符 ABC  出现多个B匹配只算一个
        int validateCharCount = 0;
        while (left <= right && right < tChar.length) {
            //当前字符
            char curChar = tChar[right];
            //当前字符以及出现多少次
            Integer curCount = tMap.getOrDefault(curChar, 0);
            //加入滑动窗口字符map数目++
            tMap.put(curChar, curCount + 1);
            //如果包含 说明最起码是ABC 里面的三个字符之一 这是有效的第一个条件 你是个D就不算有有效了
            //curCount + 1 是当前滑动窗内字符的数目 小于等于原字符数量
            //比如 ABC  出现两个B在窗口内也不算数
            if (sMap.containsKey(curChar) && curCount + 1 <= sMap.get(curChar)) {
                validateCharCount++;
            }
            //删除无用字符
            while (left < t.length()) {
                //可能需要删除的字符
                char charMayBeRemove = tChar[left];
                //这个字符在窗口在滑动窗口中的数目
                Integer tCount = tMap.getOrDefault(charMayBeRemove, 0);
                //应该出现的数目 -1 表示这个字符无用
                Integer sCount = sMap.getOrDefault(charMayBeRemove, -1);
                //tCount > sCount 表示两个情况 ===》
                // 1.当前窗口左边界字符有效但是存在多个 如
                //AAABC 找ABC 虽然A有效但是需要删除
                //2. 前窗口左边界字符无效
                //DABC 找ABC 这个D是无效的 这个时候 sCount=-1
                if (left < right && tCount > sCount) {
                    left++;
                    tMap.put(charMayBeRemove, Math.max(0, tCount - 1));
                } else {
                    break;
                }
            }
            //有效字符数 够了
            if (validateCharCount >= sChars.length) {
                //没有初始化代表之前没有满足的   或者长度大于当前的
                if (ans == null || ans.length() > right - left) {
                    //刷新
                    ans = t.substring(left, right + 1);
                }
            }
            //右边界继续++
            right++;
        }
        //找不到 返回空白
        return ans == null ? "" : ans;
    }


}
